package DataStructrue.tree;

import java.util.ArrayDeque;
import java.util.Deque;

//平衡二叉查找树
public class BBSTree<K extends Comparable<K>,V> {
    private Node root;//根节点
    private int N;//节点数量

    //节点类
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;
        private int h;//以该节点为根的树的高度
        private boolean ltag;//左子节点是否为线索
        private boolean rtag;//右子节点是否为线索
        public Node(K key,V value,Node left,Node right) {
            this.key=key;
            this.value=value;
            this.left=left;
            this.right=right;
            this.h=1;
            this.ltag=false;
            this.rtag=false;
        }
    }


    //树的大小
    public int size(){
        return N;
    }
    //判空
    public boolean isEmpty(){
        return N==0;
    }
    //添加节点
    public void put(K key,V value){
        root=put(root,key,value);
    }
    private Node put(Node n,K key,V value){
        if(n==null) {
            N++;//节点为空
            return new Node(key,value,null,null);
        }
        int cmp=key.compareTo(n.key);
        if(cmp>0){
            n.right=put(n.right,key,value);
            //判断是否需要旋转
            if(height(n.right)-height(n.left)==2){
                if(key.compareTo(n.right.key)>0)
                    n=leftRotate(n);//RR
                else
                    n=rightLeftRotate(n);//RL
            }
        } else if(cmp<0){
            n.left=put(n.left,key,value);
            if(height(n.left)-height(n.right)==2){
                if(key.compareTo(n.left.key)<0)
                    n=rightRotate(n);//LL
                else
                    n=leftRightRotate(n);//LR
            }
        }else
            n.value=value;//存在key,直接修改
        n.h=Math.max(height(n.left),height(n.right))+1;//更新高度
        return n;
    }
    //查找节点
    public V get(K key){
        return get(root,key);
    }
    private V get(Node n,K key){
        if(n==null)//不存在
            return null;
        int cmp=key.compareTo(n.key);
        if(cmp>0)
            return get(n.right,key);
        else if(cmp<0)
            return get(n.left,key);
        else
            return n.value;//已存在
    }
    //是否包含节点
    public boolean contains(K key){
        return get(key)!=null;
    }
    //删除节点
    public Node remove(K key){
        return remove(root,key);
    }
    private Node remove(Node n,K key){
        if(n==null)//不存在
            return null;
        //查找key对应节点
        int cmp=key.compareTo(n.key);
        if(cmp>0){
            n.right=remove(n.right,key);
        } else if(cmp<0){
            n.left=remove(n.left,key);
        } else{
            N--;
            if(n.right==null)
                n=n.left;
            else if(n.left==null)
                n=n.right;
            else{
                //查找右子树最小节点
                Node min=min(n.right);
                //替换当前节点
                n.key=min.key;
                n.value=min.value;
                n.right=remove(n.right,min.key);//删除min
            }
        }
        if(n==null) return null;
        //左子树较高
        if(height(n.left)-height(n.right)>=2){
            if(height(n.left.left)>height(n.left.right))
                return rightRotate(n);
            return leftRightRotate(n);
        }else if(height(n.right)-height(n.left)>=2){//右子树较高
            if(height(n.right.right)>height(n.right.left))
                return leftRotate(n);
            return rightLeftRotate(n);
        }
        n.h=Math.max(height(n.left),height(n.right))+1;//更新高度
        return n;
    }
    private Node leftRightRotate(Node n) {
        n.left=leftRotate(n.left);
        return rightRotate(n);
    }
    private Node rightLeftRotate(Node n) {
        n.right=rightRotate(n.right);
        return leftRotate(n);
    }
    private Node rightRotate(Node n) {
        Node ans=n.left;
        n.left=ans.right;
        ans.right=n;
        n.h=Math.max(height(n.left),height(n.right))+1;
        ans.h=Math.max(height(ans.left),n.h)+1;
        return ans;
    }
    private Node leftRotate(Node n) {
        Node ans=n.right;
        n.right=ans.left;
        ans.left=n;
        n.h=Math.max(height(n.left),height(n.right))+1;
        ans.h=Math.max(height(ans.right),n.h)+1;
        return ans;
    }
    //返回最小键
    public K min(){
        return min(root).key;
    }
    private Node min(Node n){
        if(n.left!=null)
            return min(n.left);
        return n;
    }
    //返回最大键
    public K max(){
        return max(root).key;
    }
    private Node max(Node n){
        if(n.right!=null)
            return max(n.right);
        return n;
    }
    //树的最大深度(根节点为1)
    public int height(Node n){
        return n==null?0:n.h;
    }

    //前序遍历
    public Deque<K> preErgodic(){
        return recursivePreErgodic(root,new ArrayDeque<>());
    }
    //递归
    private Deque<K> recursivePreErgodic(Node n,Deque<K> keys){
        if(n==null)
            return null;
        keys.add(n.key);
        recursivePreErgodic(n.left,keys);
        recursivePreErgodic(n.right,keys);
        return keys;
    }
    //层序遍历
    public Deque<K> layerErgodic(){
        Deque<Node> q=new ArrayDeque<>();
        q.add(root);
        return recursiveLayerErgodic(q,new ArrayDeque<>());
    }
    //非递归
    public Deque<K> nonRecursiveLayerErgodic(){
        Deque<K> keys=new ArrayDeque<>();
        Deque<Node> q=new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            Node n= q.poll();
            keys.add(n.key);
            if(n.left!=null)
                q.add(n.left);
            if(n.right!=null)
                q.add(n.right);
        }
        return keys;
    }
    //递归
    public Deque<K> recursiveLayerErgodic(Deque<Node> q,Deque<K> keys){
        if(q.isEmpty()) return keys;
        Node n=q.poll();
        keys.add(n.key);
        if(n.left!=null)
            q.add(n.left);
        if(n.right!=null)
            q.add(n.right);
        return recursiveLayerErgodic(q,keys);
    }
    //由前序遍历和中序遍历构建树
    public Node build(String pre,String in){
        return null;
    }

    //中序线索化
    public void inThread(){inThread(root,null).rtag=true;}
    private Node inThread(Node n,Node pre){
        if(n==null) return null;
        if(n.left!=null)//如果左子树不为空,获取左子树中序最后一个为当前节点前驱
            pre=inThread(n.left,pre);
        //当前节点的左子节点线索化
        if(n.left==null){
            n.left=pre;
            n.ltag=true;
        }
        //前驱节点的右子节点线索化
        if(pre!=null&&pre.right==null){
            pre.right=n;
            pre.rtag=true;
        }
        if(n.right!=null)//如果右子树不为空,返回右子树中序最后一个作为下一节点前驱
            pre=inThread(n.right,n);
        else pre=n;//否则当前节点即为中序最后一个
        return pre;
    }



}
